Polya Urn Latent Dirichlet Allocation: a doubly sparse massively parallel sampler

摘要

Latent Dirichlet Allocation (LDA) is a topic model widely used in naturallanguage processing and machine learning. Most approaches to training the modelrely on iterative algorithms, which makes it difficult to run LDA on big datasets that are best analyzed in parallel and distributed computationalenvironments. Indeed, current approaches to parallel inference either don'tconverge to the correct posterior or require storage of large dense matrices inmemory. We present a novel sampler that overcomes both problems, and we showthat this sampler is faster, both empirically and theoretically, than previousGibbs samplers for LDA. We do so by employing a novel P\'{o}lya-Urn-basedapproximation in the sparse partially collapsed sampler for LDA. We prove thatthe approximation error vanishes with data size, making our algorithmasymptotically exact, a property of importance for large-scale topic models. Inaddition, we show, via an explicit example, that -- contrary to popular beliefin the topic modeling literature -- partially collapsed samplers can be moreefficient than fully collapsed samplers. We conclude by comparing theperformance of our algorithm with that of other approaches on well-knowncorpora.